

/*
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.
Example:

Input: "cbbd"

Output: "bb"

*/
#include <iostream>
#include <map>
#include <string>
#include <deque>
#include <stack>
#include <vector>
#include <set>


std::string longestPalindrome(std::string s)
{
    while (s.size() <= 1) {
        return s;
    }
    std::string tmp;
    for (int i = 0; i != s.size(); ++i) {
        tmp.append("#");
        tmp += s[i];
    }
    tmp.append("#");
    
    
    int arr[10000];
    memset(arr, 0, sizeof(arr));
    for (int i = 0; i != tmp.size(); ++i) {
        arr[i] = 1;
        int pre = i - 1, suf = i + 1;
        for (; pre >= 0 && suf <= tmp.size() - 1; pre--, suf++) {
            if(tmp[pre] == tmp[suf]) {
                arr[i]++;
            } else {
                break;
            }
        }
    }
    int maxIdx = 0, max = 0;
    for (int i = 0; i != 10000 && arr[i] >= 0; ++i) {
        if (max < arr[i]) {
            max = arr[i];
            maxIdx = i;
        }
    }
    return s.substr((maxIdx - max + 1) / 2, max - 1);
}

int main(int argc, const char * argv[])
{
    std::string rst = longestPalindrome("babad");
    return 0;
}
